package de.uniLuebeck.tcs.algorithmics;

public class SudokuInstance {

	private int[] m_fields;
	private int m_rows;
	private int m_cols;
	private int m_emptyValue = 0;
	private int m_openFields;
	private int m_emptyField;
	private int m_initialOpenFields;
	private String m_fileName;

	private boolean m_isFeasible = true;

	/**
	 * Erzeugt aus einer Matrix eine Instanz
	 * 
	 * @param matrix
	 * @param filename
	 */
	public SudokuInstance(int[][] matrix, String filename) {
		m_openFields = 0;
		m_emptyField = 0;
		m_rows = matrix.length;
		m_cols = matrix[0].length;
		m_fileName = filename;

		m_fields = new int[m_rows * m_cols];
		for (int row = 0; row < m_rows; row++) {
			for (int col = 0; col < m_cols; col++) {
				m_fields[decodeCoordinate(row, col)] = matrix[row][col];
				if (m_emptyValue == matrix[row][col]) {
					m_openFields++;
				}
			}
		}
	}

	/**
	 * Erzeugt aus einem Vektor eine Instanz
	 * @param fields
	 * @param filename
	 */
	public SudokuInstance(int[] fields, String filename) {
		m_openFields = 0;
		m_emptyField = 0;
		m_rows = (int) Math.sqrt(fields.length);
		m_cols = m_rows;
		m_fileName = filename;

		m_fields = fields;
		for (int i = 0; i < m_fields.length; i++) {
			if (isEmpty(i)) {
				m_openFields++;
			}
		}

		m_initialOpenFields = m_openFields;
	}

	/**
	 * Fertigt eine Kopie einer Instanz an
	 * 
	 * @param x
	 */
	public SudokuInstance(SudokuInstance x) {
		m_fields = x.m_fields.clone();
		m_isFeasible = x.isFeasible();
		m_openFields = x.m_openFields;
		m_emptyField = x.m_emptyField;
		m_rows = x.m_rows;
		m_cols = x.m_cols;
		m_fileName = x.m_fileName;
		m_initialOpenFields = x.m_initialOpenFields;
	}

	/**
	 * Berechnet aus den Feldkoordinaten den Feld-Index.
	 * 
	 * @param row
	 * @param col
	 * @return
	 */
	private int decodeCoordinate(int row, int col) {
		return (row * m_cols + col);
	}

	/**
	 * Liefert den Wert eines Feldes in einem Vektor
	 * @param i
	 * @return
	 */
	public int getField(int i) {
		return m_fields[i];
	}

	/**
	 * Liefert den Wert eines Feldes in einer Matrix
	 * @param row
	 * @param col
	 * @return
	 */
	public int getField(int row, int col) {
		return m_fields[decodeCoordinate(row, col)];
	}

	/**
	 * Setzt den Wert eines Feldes in einem Vektor
	 * @param i
	 * @param value
	 */
	public void setField(int i, int value) {
		m_fields[i] = value;
		m_openFields--;

		/*
		 * Eine ungueltige Loesung bleibt ungueltig, auch wenn ein ungesetztes Feld
		 * gesetzt wurde
		 */
		if (!m_isFeasible) {
			return;
		}

		/*
		 * Falls die Loesung gueltig war, muss nur die Zeile, Spalte und der
		 * Block, in dem das gesetzte Feld liegt auf eine Aenderung der
		 * Gueltigkeit ueberprueft werden
		 */
		int row = getRowFromIndex(i);
		int col = getColumnFromIndex(i);

		int[] values_row = countValues(getValuesInRow(row));
		int[] values_col = countValues(getValuesInColumn(col));
		int[] values_block = countValues(getValuesInBlock(i));

		for (int j = 0; j < values_row.length; j++) {
			if (values_row[j] > 1 || values_col[j] > 1 || values_block[j] > 1) {
				m_isFeasible = false;
				return;
			}
		}

		m_isFeasible = true;
	}

	/**
	 * Setz den Wert eines Feldes in einer Matrix
	 * @param row
	 * @param col
	 * @param value
	 */
	public void setField(int row, int col, int value) {
		m_fields[decodeCoordinate(row, col)] = value;
	}

	/**
	 * Liefert den Index des naechsten Feldes ohne Wert
	 * 
	 * @return
	 */
	public int getNextEmpty() {
		// return m_emptyField;

		for (int i = 0; i < getNumberOfFields(); i++) {
			if (isEmpty(i)) {
				return i;
			}
		}

		return -1;
	}

	/**
	 * Gibt das Feld mit der geringsten Anzahl an Moeglichkeiten zurueck
	 * 
	 * @return
	 */
	public int[][] getNext() {

		int[][] posibleSolutions = new int[getNumberOfFields()][];
		int[][] minSolution = new int[2][];
		minSolution[0] = new int[1];
		int min_Variations = 16;
		int min_Variations_Koord = 0;

		/*
		 * Berechnen der Moeglichkeiten fuer alle freien Felder im Vektor
		 */
		for (int i = 0; i < getNumberOfFields(); i++) {
			if (isEmpty(i)) {
				posibleSolutions[i] = getPossibleValues(i);

				// Fals es nur eine Moeglichkeit gibt, trage die ein und beginne die Suche von vorn
				if (1 == posibleSolutions[i].length){
					setField(i,posibleSolutions[i][0]);
					i=0;
				}
				
				else if (posibleSolutions[i].length < min_Variations) {
					min_Variations = posibleSolutions[i].length;
					min_Variations_Koord = i;
				}
			}
		}

		/*
		 * Abspeichern der Feldnummer und der Moeglichkeiten
		 */
		minSolution[0][0] = min_Variations_Koord;
		minSolution[1] = posibleSolutions[min_Variations_Koord];

		/*
		 * Wenn es kein freies Feld gibt, wird -1 ausgegeben
		 */
		if (minSolution[1] == null) {
			minSolution[0][0] = -1;
		}

		return minSolution;
	}

	/**
	 * @see SudokuInstance::isEmpty(int, int)
	 * @param i
	 * @return
	 */
	public boolean isEmpty(int i) {
		return (m_emptyValue == getField(i));
	}

	/**
	 * Prueft, ob ein Feld einen Wert hat.
	 * 
	 * @param row
	 * @param col
	 * @return
	 */
	public boolean isEmpty(int row, int col) {
		return (m_emptyValue == getField(row, col));
	}

	/**
	 * Liefert eine Matrix, die die Instanz repraesentiert.
	 * 
	 * @return
	 */
	public int[][] getAsMatrix() {
		int[][] matrix = new int[m_rows][m_cols];
		for (int row = 0; row < m_rows; row++) {
			for (int col = 0; col < m_cols; col++) {
				matrix[row][col] = getField(row, col);
			}
		}
		return matrix;
	}

	/**
	 * Liefert die Anzahl der Zeilen
	 * 
	 * @return
	 */
	public int getNumberOfRows() {
		return m_rows;
	}

	/**
	 * Liefert die Anzahl der Spalten
	 * 
	 * @return
	 */
	public int getNumberOfCols() {
		return m_cols;
	}

	/**
	 * Gibt die Anzahl der Felder zurueck
	 * 
	 * @return
	 */
	public int getNumberOfFields() {
		return (m_rows * m_cols);
	}

	/**
	 * Gibt alle moeglichen Werte eines Fldes zurueck
	 * @param i
	 * @return
	 */
	public int[] getPossibleValues(int i) {
		int[] return_values;
		int[] values = new int[m_rows];
		// Alle MOEGLICHEN Werte zurueck geben
		for (int j = 0; j < values.length; j++) {
			values[j] = j + 1;
		}

		if (i < 0) {
			/*
			 * No Optimization
			 */
			return values;
		}

		/*
		 * Strike out Values that are in that specific row or column
		 */
		int[] row_values = getValuesInRow(getRowFromIndex(i));
		int[] column_values = getValuesInColumn(getColumnFromIndex(i));
		int[] block_values = getValuesInBlock(i);

		for (int ii = 0; ii < values.length; ii++) {
			for (int ij = 0; ij < row_values.length; ij++) {
				if (values[ii] == row_values[ij]
						|| values[ii] == column_values[ij]
						|| values[ii] == block_values[ij]) {
					values[ii] = m_emptyValue;
				}
			}
		}

		int cnt = 0;

		/*
		 * Zaehle die Werte, die noch moeglich sind.
		 */
		for (int ii = 0; ii < values.length; ii++) {
			if (m_emptyValue != values[ii]) {
				cnt++;
			}
		}

		/*
		 * Kopiere moegliche werte
		 */
		return_values = new int[cnt];
		int ij = 0;
		for (int ii = 0; ii < values.length; ii++) {
			if (m_emptyValue != values[ii]) {
				return_values[ij] = values[ii];
				ij++;
			}
		}

		return return_values;
	}

	/**
	 * Gibt die Instanz auf der Standardausgabe aus
	 */
	public void printDebug() {
		for (int row = 0; row < m_rows; row++) {
			for (int col = 0; col < m_cols; col++) {
				System.out.print(getField(row, col) + " ");
			}
			System.out.println();
		}
		System.out.println();
	}

	/**
	 * Zaehlt die Felder, die leer sind (Feldwert == 0).
	 * 
	 * @return
	 */
	public int getNumberOfOpenFields() {
		return m_openFields;
	}

	public int getNumberOfInitialOpenFields() {
		return m_initialOpenFields;
	}

	public boolean isFeasible() {
		return m_isFeasible;
	}

	/**
	 * Name des Sudokus, der aus der Eingabedatei ausgelesen wurde.
	 * 
	 * @return
	 */
	public String getSudokuName() {
		return m_fileName;
	}

	/**
	 * Zaehlt die Haeufigkeit des Vorkommen von Werten in dem Array. Nullen werden
	 * bei Zaehlen jedoch ignoriert, da die Null intern ein ungesetztes Feld
	 * repraesentiert.
	 * 
	 * @param values
	 * @return
	 */
	private int[] countValues(int[] values) {
		int[] counter = new int[m_rows];

		for (int i = 0; i < counter.length; i++) {
			counter[i] = 0;
		}

		for (int i = 0; i < values.length; i++) {
			if (m_emptyValue != values[i]) {
				counter[values[i] - 1]++;
			}
		}

		return counter;
	}

	/**
	 * Berechnet zu einem Feld-Index die passende Zeile.
	 * 
	 * @param i
	 * @return
	 */
	private int getRowFromIndex(int i) {
		return (i / m_cols);
	}

	/**
	 * Berechnet zu einem Feld-Index die passende Spalte
	 * 
	 * @param i
	 * @return
	 */
	private int getColumnFromIndex(int i) {
		return (i % m_cols);
	}

	/**
	 * Liest eine ganze Zeile aus
	 * 
	 * @param row
	 * @return
	 */
	private int[] getValuesInRow(int row) {
		int[] usedValues = new int[m_cols];

		for (int col = 0; col < m_cols; col++) {
			usedValues[col] = getField(row, col);
		}

		return usedValues;
	}

	/**
	 * Liest eine ganze Spalte aus
	 * 
	 * @param col
	 * @return
	 */
	private int[] getValuesInColumn(int col) {
		int[] usedValues = new int[m_cols];

		for (int row = 0; row < m_rows; row++) {
			usedValues[row] = getField(row, col);
		}

		return usedValues;
	}

	/**
	 * Liest einen ganzen Block aus.
	 * 
	 * @param i
	 *            Feld-Index, das Teil des Blocks ist.
	 * @return
	 */
	private int[] getValuesInBlock(int i) {
		int block_size = (int) Math.sqrt(m_rows);
		int[] usedValues = new int[m_rows];

		int row = getRowFromIndex(i);
		int col = getColumnFromIndex(i);

		// Block-Koordinaten
		int row_block = row / block_size;
		int col_block = col / block_size;

		int j = 0;
		for (int i_row = 0; i_row < block_size; i_row++) {
			for (int i_col = 0; i_col < block_size; i_col++) {
				usedValues[j] = getField(row_block * block_size + i_row,
						col_block * block_size + i_col);
				j++;
			}
		}

		return usedValues;
	}

}
